package leetcode_1601_1700;

import java.sql.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

public class LeeCode_1673 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(mostCompetitive(new int[]{3, 5, 2, 6}, 2)));
//        System.out.println(Arrays.toString(mostCompetitive(new int[]{2,4,3,3,5,4,9,6}, 4)));
//        System.out.println(Arrays.toString(mostCompetitive(new int[]{71,18,52,29,55,73,24,42,66,8,80,2}, 3)));
//        System.out.println(Arrays.toString(mostCompetitive(
//                new int[]{84,10,71,23,66,61,62,64,34,41,80,25,91,43,4,75,65,13,37,41,46,90,55,8,85,61,95,71}, 24)));
    }
    private static int[] mostCompetitive(int[] nums, int k) {
        int n = nums.length, delete = n - k;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && delete > 0 && stack.peek() > nums[i]){
                stack.pop();
                delete--;
            }
            stack.push(nums[i]);
        }
        while (delete > 0){
            delete--;
            stack.pop();
        }
        int[] subsequence = new int[k];
        for (int i = k-1; i >= 0; i--) {
            subsequence[i] = stack.pop();
        }
        return subsequence;
    }
}
